\chapter{数据结构理论}
\section{线性表}
线性表简称表,是零个或多个元素的有穷序列,通常可以表示成$k_0 ,k_1 , \ldots,k_{n-1} (n \geq 1)$
\begin{itemize}
	\item 表目:线性表中的元素(可包含多个数据项、记录)
	\item 索引(下标):$i$ 称为表目 $k_i$ 的“索引”或“下标”
	\item 表的长度:线性表中所含元素的个数 n
	\item 空表:长度为零的线性表 ( n = 0 )
\end{itemize}
\textbf{线性表特点:}操作灵活,其长度可以增长、缩短。\\
\begin{itemize}
	\item 有一个唯一的开始结点,它没有前驱,有一个唯一的直接后继。
	\item  一个唯一的终止结点,它有一个唯一的直接前驱,而没有后继。
	\item 其它的结点皆称为内部结点,每一个内部结点都有且仅有一个唯一的直
	      接有前驱,也有一个唯一的直接后继。
	      $<a_i,a_{i+1}>a_i$ 是$a_{i+1}$ 的前驱,$a_{i+1}$是$a_i$ 的后继
	\item 前驱/后继关系r,具有反对称性和传递性
\end{itemize}
\begin{figure}[!ht]
	\centering
	\includegraphics[width=\textwidth]{list}
	\caption{链式结构}
\end{figure}
\textbf{线性结构的特点}
\begin{itemize}
	\item 均匀性:虽然不同线性表的数据元素可以是各种各样的,但对于同一线性表的各数据元素必定具有相同的数据类型和长度。
	\item 有序性:各数据元素在线性表中都有自己的位置,且数据元素之间的相对位置是线性的。
\end{itemize}
\textbf{线性结构的分类}
\begin{itemize}
	\item 按复杂程度划分
	      \begin{itemize}
		      \item 简单的:线性表、栈、队列、散列表。
		      \item 高级的:广义表、多维数组、文件……。
	      \end{itemize}
	\item 按访问方式划分
	      \begin{itemize}
		      \item 直接访问型
		      \item 顺序访问型
		      \item 目录索引型
	      \end{itemize}
	\item 按操作划分
	      \begin{itemize}
		      \item 线性表
		            \begin{itemize}
			            \item 所有表目都是同一类型结点的线性表。
			            \item 不限制操作形式。
			            \item 根据存储的不同分为:顺序表,链表。
		            \end{itemize}
		      \item 栈（LIFO）插入和删除操作都限制在表的同一端进。
		      \item 队列（FIFO）插入操作在表的一端, 删除操作在另一端。
	      \end{itemize}
\end{itemize}
线性表的主要属性包括：
\begin{itemize}
	\item 表头
	\item 线性表的长度
	\item 表头 (head)
	\item 表尾 (tail)
	\item 当前位置 (current position)
\end{itemize}
\textbf{顺序表}
\begin{itemize}
	\item 按索引值从小到大存放在一片相邻的连续区域。
	\item 紧凑结构,存储密度为 1。
\end{itemize}
\subsection{线性表实现方法的比较}
顺序表的主要优点
\begin{itemize}
	\item 没有使用指针,不用花费额外开销
	\item 线性表元素的读访问非常简洁便利
\end{itemize}
\textbf{链表的主要优点}：
\begin{itemize}
	\item  无需事先了解线性表的长度
	\item  允许线性表的长度动态变化
	\item  能够适应经常插入删除内部元素的情况
\end{itemize}
\textbf{总结}：
\begin{itemize}
	\item 顺序表是存储静态数据的不二选择。
	\item 链表是存储动态变化数据的良方。
\end{itemize}
\textbf{顺序表}
\begin{itemize}
	\item 插入、删除运算时间代价 $O(n)$,查找则可常数时间完成
	\item 预先申请固定长度的连续空间
	\item 如果整个数组元素很满,则没有结构性存储开销
\end{itemize}
\textbf{链表}\\
\begin{itemize}
	\item 插入、删除运算时间代价 $O(1)$,但找第$i$个元素运算时间代价 $O(n)$。
	\item 存储利用指针,动态地按照需要为表中新的元素分配存储空间。
	\item 每个元素都有结构性存储开销。
\end{itemize}
\textbf{顺序表和链表存储密度}
\begin{enumerate}
	\item n 表示线性表中当前元素的数目。
	\item P 表示指针的存储单元大小(通常为 4 bytes)。
	\item E 表示数据元素的存储单元大小。
	\item D 表示可以在数组中存储的线性表元素的最大数目。
\end{enumerate}
\textbf{空间需求}:
\begin{itemize}
	\item 顺序表的空间需求为 $DE$
	\item 链表的空间需求为 $n(P + E)$
\end{itemize}
$n$ 的临界值,即 $n > DE / (P+E)$
\begin{itemize}
	\item $n$ 越大,顺序表的空间效率就更高。
	\item 如果$P = E$,则临界值为 $n = D / 2$。
\end{itemize}
顺序表不适用的场合
\begin{itemize}
	\item  经常插入删除时,不宜使用顺序表。
	\item  线性表的最大长度也是一个重要因素。
\end{itemize}
\textbf{链表不适用的场合}
\begin{itemize}
	\item 当读操作比插入删除操作频率大时,不应选择链表。
	\item 当指针的存储开销,和整个结点内容所占空间相比其比例较大时,应该慎重选择。
\end{itemize}
\textbf{顺序表和链表的选择}\\
顺序表
\begin{itemize}
	\item 结点总数目大概可以估计
	\item 线性表中结点比较稳定(插入删除少)
	\item $n > DE / (P + E)$
\end{itemize}
\textbf{链表}\\
\begin{itemize}
	\item 结点数目无法预知。
	\item 线性表中结点动态变化(插入删除多)。
	\item $n < DE / (P + E)$。
\end{itemize}

\textbf{链表}
\begin{itemize}
	\item 单链
	\item 双链
	\item 循环链
\end{itemize}
\begin{figure}[!ht]
	\centering
	\includegraphics[width=\textwidth]{linear_table}
	\caption{链表种类}
	\label{fig:link_type}
\end{figure}
栈（LIFO）插入和删除在表的同一端进行
\begin{figure}[!ht]
	\centering
	\includegraphics[width=.5\textwidth]{linear_stack}
	\caption{栈的结构}
\end{figure}
\textbf{队列}：插入在表的一端，删除在表的另一端。
\textbf{线性表的类模板}
% TODO: list的AST
% \cppfile[firstline=1,lastline=23]{code/datastruct/tree/include/list.h}
为了方便调试代码中添加了用于显示输出相关的成员函数。
% \cppfile[firstline=24,lastline=71]{code/datastruct/tree/include/list.h}
\subsection{顺序表}
\textbf{顺序表：}也称向量,采用定长的一维数组存储结构

\textbf{主要特性：}
\begin{itemize}
	\item 元素的类型相同。
	\item 元素顺序地存储在连续存储空间中,每一个元素有唯一的索引值。
	\item 使用常数作为向量长度。
	\item 数组存储。
	      \begin{itemize}
		      \item  读写其元素很方便 ,通过下标即可指定位置。
		      \item  只要确定了首地址,线性表中任意数据元素都可以随机存取。
	      \end{itemize}
\end{itemize}
\begin{figure}
	\centering
	\includesvg[width=\textwidth]{linear_array}
	\caption{线性表存储示意图}
	\label{fig:linear_array_and_address}
\end{figure}
元素地址计算如$Loc(k_i)=Loc(k_0)+c\times i,c=sizeof(ELEM)$
\subsubsection*{顺序表的类定义}
顺序表要实现的功能有:
\begin{itemize}
	\item 清空顺序表(\cppinline{void clear()})
	\item 判断顺序表是否为空(\cppinline{void isEmpty()})
	\item 在顺序表尾部添加元素\cppinline{(bool append(const T value))}
	\item 在位置p删除元素\cppinline{(bool insert(const int p,const T value))}
	\item 获取值为value的索引(\cppinline{bool delete(const int p))}
	\item 获取位置p的元素\cppinline{value(bool getPos(int& p,const T value))}
	\item 设置位置p的元素\cppinline{(bool setValue(const int p,const T value));}
\end{itemize}

% \cppfile{code/DS/ex4/main.cpp}
顺序表插入示意\figref{fig:linear_array_and_address}
\begin{figure}[!htb]
	\centering
	\includesvg[width=\textwidth]{link_insert_node}
	\caption{顺序表插入示意图}
	\label{fig:link_insert_node}
\end{figure}
顺序表和插入代码：
\begin{longlisting}
	\caption{顺序表插入元素}
	\cppfile[firstline=7,lastline=23]{third_party/coding/cxx/datastruct/linear/src/arrList.cc}
	\label{code:arr_list_insert}
\end{longlisting}
\begin{figure}
	\centering
	\includesvg[width=0.5\textwidth]{vec_array_delete}
	\caption{删除示意图}
	\label{fig:vec_array_delete}
\end{figure}
顺序表删除示意\figref{fig:vec_array_delete}
\begin{longlisting}
	\caption{顺序表删除指定位置的元素}
	\cppfile[firstline=25,lastline=41]{third_party/coding/cxx/datastruct/linear/src/arrList.cc}
	\label{code:arr_list_delete}
\end{longlisting}
顺序表插入时间代价$M_i=\frac{n}{2}$,删除时间代价$M_d=\frac{n-1}{2}$
\subsection{链表}
通过指针把它的一串存储结点链接成一个链,存储结点由两部分组成:
\begin{itemize}
	\item 数据域。
	\item 指针域(指向后继节点的地址)。
\end{itemize}
\begin{figure}[!ht]
	\centering
	\includesvg[width=\textwidth]{link_list_types}
	\caption{常见链表类型}
	\label{fig:link_list_types}
\end{figure}
\figref{fig:link_type} 中链表头尾使用了一个特殊的节点，这样在部分算法中判断首尾链表会非常方便。
\subsubsection{单链表}
单链表节点数据结构包括数据域和指针域。数据域用来存储数据元素的值，指针域用来指向下一个节点。
\begin{cpp}
template<typename T>
class Node{
  T value;
  Node *next;
}
\end{cpp}
单链表应该包含的功能:
\begin{itemize}
	\item 删除单链表中的一个元素。
	\item 获取单链表中的一个元素。
	\item 修改单链表中的一个元素。
	\item 清除单链表。
	\item 获取单链表的长度。
\end{itemize}
\textbf{带头节点的单链表：}
\begin{itemize}
	\item 整个单链表：head
	\item 第一个节点：head->next,head$\neq$nullptr
	\item 空表判断：head->next == nullptr
\end{itemize}
% % \cppfile[firstline=7,lastline=18]{code/datastruct/tree/src/LinkNode.cpp}
单链表的类定义：
\begin{longlisting}
	\caption{单链表ADT定义}
	\cppfile[firstline=3,lastline=21]{third_party/coding/cxx/datastruct/linear/include/linkList.hpp}
	\label{code:linklist_funcs}
\end{longlisting}
查找单链表中第i个节点
\textbf{单链表的插入示意图：}
\begin{figure}[!ht]
	\centering
	\includesvg[width=\textwidth]{link_insert_node}
	\caption{单链表插入}
	\label{fig:link_insert}
\end{figure}
单链表插入新节点：
\begin{enumerate}
	\item 创建新节点
	\item 新节点指向插入位置右边的节点
	\item 插入位置的左边节点指向新节点
\end{enumerate}
\begin{longlisting}
	\caption{单链表特定位置插入节点}
	\cppfile[firstline=42,lastline=58]{third_party/coding/cxx/datastruct/linear/src/linkNode.cc}
	\label{code:arr_list_delete}
\end{longlisting}

\textbf{单链表的删除}
从链表中删除节点
\begin{enumerate}
	\item 用p指向元素x的节点的前驱结点
	\item 释放元素x的结点
	\item 释放x占据的空间
\end{enumerate}
\begin{figure}[!ht]
	\centering
	% \includegraphics[width=\textwidth]{ds_7}
	\includesvg[width=\textwidth]{link_delete_node}
	\caption{链表删除节点q}
\end{figure}
\begin{cpp}
// 删除节点
q = p->next;
p->next = q->next;
free(q);
\end{cpp}
删除节点的算法：
% \cppfile[firstline=132,lastline=147]{code/datastruct/tree/src/LinkNode.cpp}
对一个结点操作,必先找到它,即用一个指针指向它。
\begin{itemize}
	\item 找单链表中任一结点,都必须从第一个点开始
	      \begin{Textcode}
		      p = head;
		      while (没有到达) p = p->next;
	      \end{Textcode}
	\item 单链表的时间复杂度
	      \begin{itemize}
		      \item 定位:$O(n)$
		      \item 插入：$O(x)+O(1)$
		      \item 删除：$O(n)+O(1)$
	      \end{itemize}
\end{itemize}
单链表的next字段仅仅指向后继节点，不能有效的查找前去，反之亦然。添加指向前驱的指针
\subsubsection{双链表}
\begin{figure}[H]
	\centering
	\includegraphics[width=0.5\textwidth]{bi_linklistnode}
	\caption{双链节点示意图}
	\label{fig:bi_linklistnode}
\end{figure}
双链结构示意图如\figref{fig:bi_linklist}：
\begin{figure}[!ht]
	\centering
	\includegraphics[width=\textwidth]{bi_linklist}
	\caption{双链示意图}
	\label{fig:bi_linklist}
\end{figure}
双链节点和结构定义：
\begin{longlisting}
	\caption{双链节点ADT}
	\cppfile[firstline=2,lastline=19]{third_party/coding/cxx/datastruct/linear/include/link.hpp}
	\label{code:bi_link}
\end{longlisting}
\begin{figure}[!htbp]
	\centering
	\includesvg[width=\textwidth]{bilink_node_insert}
	\caption{双向链表插入示意图}
	\label{fig:bilink_node_delete}
\end{figure}
\figref{fig:blink_node_delete}是删除节点的示意图
\begin{figure}[!htbp]
	\centering
	\includesvg[width=\textwidth]{blink_node_delete}
	\caption{双向链表删除节点}
	\label{fig:blink_node_delete}
\end{figure}

% \begin{figure}
% 	\centering
% 	\includegraphics[width=\textwidth]{ds_11}
% 	\caption{双链删除节点}
% 	\label{fig:ds_11}
% \end{figure}
\begin{cpp}
p->prev->next=p->next
p->next->prev=p->prev
p->next=nullptr
p->prev=nullptr
\end{cpp}
\subsubsection{循环链}
将单链表或者双链表的头尾结点链接起来,就是一个循，环链表，不增加额外存储花销,却给不少操作带来了方便， 从循环表中任一结点出发,都能访问到表中其他结点。循环链示意\figref{fig:bi_list_cycle}
\begin{figure}[!ht]
	\centering
	\includesvg[width=\textwidth]{bi_list_cycle}
	\caption{循环链示意图}
	\label{fig:bi_list_cycle}
\end{figure}
\subsubsection*{链表的边界条件}
\begin{itemize}
	\item 几个特殊点的处理
	      \begin{itemize}
		      \item  头指针处理
		      \item  非循环链表尾结点的指针域保持为 nullptr
		      \item  循环链表尾结点的指针回指头结点
	      \end{itemize}
	\item 链表处理
	      \begin{itemize}
		      \item 空链表的特殊处理
		      \item 插入或删除结点时指针勾链的顺序
		      \item 指针移动的正确性
		      \item 插入
		      \item 查找或遍历
	      \end{itemize}
\end{itemize}
% \subsection{数据结构应用}
% 农夫过河，现在有农夫，羊，狼，人，菜。农夫每次能带一个物品过河，羊和狼，羊和菜不能在人不在的时候在同一边，输出过河方式。
% \cppfile{code/STL/arith/main.cpp}
\subsection{创建基本的数据结构}
\subsection{栈和队列}
\begin{itemize}
	\item 栈 (Stack)：运算只在表的一端进行。 
	\item 队列 (Queue)：运算只在表的两端进行。
\end{itemize}
栈的ADT：
\begin{longlisting}
	\caption{顺序栈的ADT}
	\cppfile{third_party/coding/cxx/datastruct/linear/include/stack.hpp}
	\label{code:stack_adt}
\end{longlisting}
顺序栈 (Array-based Stack)
\begin{itemize}
	\item 使用向量实现,本质上是顺序表的简化版
	\item 关键是确定哪一端作为栈顶
	\item 上溢 (Overflow)当栈中已经有 size 个元素时,如果再做进栈运算,所产生的现象
	\item 下溢 (Underflow) 对空栈进行出栈运算时所产生的现象,下溢问题
\end{itemize}
\textbf{链式栈(Linked Stack)}用单链表方式存储,其中指针的方向是从栈顶向下
链接
\begin{longlisting}
	\caption{顺序栈入栈}
	\cppfile[firstline=14,lastline=22]{third_party/coding/cxx/datastruct/linear/src/stack.cc}
	\label{code:stack_push}
\end{longlisting}

\begin{longlisting}
	\caption{栈顶操作代码框架}
	\cppfile[firstline=14,lastline=22]{third_party/coding/cxx/datastruct/linear/src/stack.cc}
	\label{code:stack_pop}
\end{longlisting}
% \textbf{栈顶操作代码框架}
% \begin{cpp}
% bool arrStack<T>::pop(T & item) { // 出栈
% if (top == -1) {                  // 栈为空
% 	cout << "栈为空,不能执行出栈操作"<< endl;
% 	return false;
% } else {
% 	item = st[top--]; // 返回栈顶,并缩减1
% 	return true;
% }
% }
% \end{cpp}
顺序栈的实现：
% \cppfile{code/DS/ex7/Stack.hpp}
测试代码：
% \cppfile{code/DS/ex7/main.cpp}
\textbf{链式栈的定义}\\
用单链表方式存储，指针的方向从栈顶向下链接。示意图如\ref{fig:link_stack}
\begin{figure}[!htb]
	\centering
	% \includegraphics[width=0.5\textwidth]{ds_16}
	\includesvg[width=0.5\textwidth]{link_stack}
	\caption{链式栈示意图}
	\label{fig:link_stack}
\end{figure}
\begin{longlisting}
	\caption{链式栈创建}
	\cppfile[firstline=2,lastline=5]{third_party/coding/cxx/datastruct/linear/src/linkstack.cc}
	\label{code:link_stack_create}
\end{longlisting}
\begin{longlisting}
	\caption{压栈操作}
	\cppfile[firstline=21,lastline=26]{third_party/coding/cxx/datastruct/linear/src/linkstack.cc}
	\label{code:link_stack_push}
\end{longlisting}

\begin{longlisting}
	\caption{从单链栈弹出元素}
	\cppfile[firstline=7,lastline=19]{third_party/coding/cxx/datastruct/linear/src/linkstack.cc}
	\label{code:link_stack_pop}
\end{longlisting}

\textbf{顺序栈和链式栈的比较}
\begin{itemize}
	\item  时间效率
	      \begin{itemize}
		      \item 所有操作都只需常数时间
		      \item 顺序栈和链式栈在时间效率上难分伯仲
	      \end{itemize}
	\item 空间效率
	      \begin{itemize}
		      \item 顺序栈须说明一个固定的长度
		      \item 链式栈的长度可变,但增加结构性开销
	      \end{itemize}
\end{itemize}
实际应用中,顺序栈比链式栈用得更广泛：
\begin{itemize}
	\item  顺序栈容易根据栈顶位置,进行相对位移,快速定位并读取栈的内部元素。
	\item  顺序栈读取内部元素的时间为$O(1)$,而链式栈则需要沿着指针链游走,显然慢些,读取第$k$个元素需要时间为$O(k)$。
\end{itemize}

\emph{ 一般来说,栈不允许“读取内部元素”,只能在栈顶操作。}
\subsubsection{栈的应用}
栈的特点:后进先出,体现了元素之间的透明性。常用来处理具有递归结构的数据：
\begin{itemize}
	\item 深度优先搜索
	\item 表达式求值
	\item 子程序/函数调用的管理
	\item 消除递归
\end{itemize}
\nameref{sec:express_tree} 常用来计算表达式的值。
\begin{itemize}
	\item 表达式的递归定义
	      \begin{itemize}
		      \item 基本符号集:{0,1,...,9,+,-,*,/,(,)}
		      \item 语法成分集:{<表达式> , <项> , <因子> , <常数>, <数字> }
	      \end{itemize}
	\item 中缀表达23+(34*45)/(5+6+7)式
	\item 后缀表达式23 34 45 * 5 6 7 + + / +
\end{itemize}

\textbf{计算中缀表达式}
表达式：4 * x * (2 * x + a) – c
\begin{itemize}
	\item 运算符在中间
	\item 需要括号改变优先级
\end{itemize}
中缀表达式\figref{fig:mid_express}。
\begin{figure}[!ht]
	\centering
	\includesvg[width=0.5\textwidth]{mid_express}
	\caption{中缀表达式图}
	\label{fig:mid_express}
\end{figure}
中缀表达式文法公式：
\begin{Textcode}
expression = term { ("+" | "-") term } ;
term       = factor { ("*" | "/") factor } ;
factor     = primary [ "^" factor ] ;
primary    = number | identifier | "(" expression ")" ;
number     = digit { digit } ;
identifier = letter { letter | digit } ;
digit      = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
letter     = "a" | "b" | ... | "z" | "A" | "B" | ... | "Z" ;
\end{Textcode}
\begin{itemize}
	\item expression 由一个 term 开始，后跟零个或多个由 + 或 - 连接的 term。这体现了加法和减法的左结合性以及较低的优先级。
	\item term 由一个 factor 开始，后跟零个或多个由 * 或 / 连接的 factor。这体现了乘法和除法的左结合性以及比加法和减法更高的优先级。
	\item factor 由一个 primary 开始，后跟可选的 \^ 运算符和另一个 factor。这体现了乘方的右结合性和较高的优先级。
	\item primary 可以是一个 number，一个 identifier (变量名)，或者一个被括号 () 包裹的 expression，用于改变优先级。
	\item number 和 identifier 的定义是基本的词法规则。
\end{itemize}
将 23 + (34 * 45) / (5 + 6 + 7) 与 EBNF 对应：
\begin{enumerate}
	\item 23: 对应 number，因为 '2' 和 '3' 都是 digit，并且 number 可以是 digit 后面跟着零个或多个 digit。最终，23 是一个 primary，因为 primary 可以是 number。
	\item +: 对应 "+" | "-" 在 expression 的规则中。它连接了左边的 term (23) 和右边的另一个 term ((34 * 45) / (5 + 6 + 7) 的结果)。
	\item (34 * 45) / (5 + 6 + 7): 这是一个更复杂的结构，它对应一个 term。
		\begin{itemize}
			\item (34 * 45): 对应 primary 中的 "(" expression ")"。
				\begin{itemize}
					\item 内部的 34 对应 number，是 primary。
					\item 内部的 * 对应 "*" 或 "/" 在 term 的规则中。
					\item 内部的 45 对应 number，是 primary。
					\item 因此，34 * 45 对应一个 term (由 factor '*' factor 构成，而 factor 是 primary)。
				\end{itemize}
			\item /: 对应 "*" 或 "/" 在 term 的规则中，连接了左边的 term ((34 * 45) 的结果) 和右边的另一个 factor ((5 + 6 + 7) 的结果)。
			\item (5 + 6 + 7): 对应 primary 中的 "(" expression ")"。
				\begin{itemize}
					\item 内部的 5 对应 number，是 primary，也是一个 term。
					\item 内部的第一个 + 对应 "+" | "-" 在 expression 的规则中。
					\item 内部的 6 对应 number，是 primary，也是一个 term。
					\item 内部的第二个 + 对应 "+" | "-" 在 expression 的规则中。
					\item 内部的 7 对应 number，是 primary，也是一个 term。
					\item 因此，5 + 6 + 7 对应一个 expression (由 term '+' term '+' term 构成，而 term 是 primary)。
				\end{itemize}
		\end{itemize}
\end{enumerate}
总结对应关系:
\begin{itemize}
	\item 23 -> number -> primary -> term -> expression (作为 expression 的第一个 term)
	\item + -> "+" | "-" (连接 expression 中的 term)
	\item (34 * 45) -> ("(" expression ")") -> ("(" term ")") -> ("(" factor ("*" factor) ")") -> ("(" primary ("*" primary) ")")
	\item / -> "*" | "/" (连接 term 中的 factor)
	\item (5 + 6 + 7) -> ("(" expression ")") -> ("(" term ("+" term ("+" term)) ")") -> ("(" primary ("+" primary ("+" primary)) ")")
\end{itemize}
最终，整个表达式 23 + (34 * 45) / (5 + 6 + 7) 符合 expression = term { ("+" | "-") term } 的规则，其中第一个 term 是 23，第二个 term 是 (34 * 45) / (5 + 6 + 7)。而第二个 term 又符合 term = factor { ("*" | "/") factor } 的规则。

这个例子展示了中缀表达式的结构如何被 EBNF 语法规则所描述和约束，确保了表达式的合法性和可解析性。EBNF 提供了一种形式化的方式来定义语言（包括表达式）的结构。
表达式的递归图示\ref{fig:mid_express}
% \begin{figure}[!ht]\label{fig:ds_16}
% 	\centering
% 	\includegraphics[width=0.5\textwidth]{ds_18}
% 	\caption{表达式的递归图示}
% \end{figure}
后缀表达式\ref{fig:ds_19}：4 x * 2 x * a + * c –
\begin{itemize}
	\item 运算符在后面
	\item 完全不需要括号
\end{itemize}
\begin{figure}[!ht]
	\centering
	\includegraphics[width=0.5\textwidth]{ds_19}
	\caption{后缀表达式}
	\label{fig:ds_19}
\end{figure}
后缀表达式
\begin{Textcode}
expression = operand | expression expression operator ;
operand    = number | identifier ;
operator   = "+" | "-" | "*" | "/" | "^" ; // 可以包含更多运算符
number     = digit { digit } ;
identifier = letter { letter | digit } ;
digit      = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
letter     = "a" | "b" | ... | "z" | "A" | "B" | ... | "Z" ;
\end{Textcode}
% \begin{Textcode}
% 	<表达式>::=<项> <项> +
% 	| <项> <项> -
% 	| <项>
% 	<项>
% 	::= <因子> <因子> *
% 	| <因子> <因子> /
% 	| <因子>
% 	<因子>::=<常数>
% 	<常数>::=<数字>
% 	| <数字> <常数>
% 	<数字>::=0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
% \end{Textcode}
后缀表达式求值
\begin{itemize}
	\item  循环:依次顺序读入表达式的符号序列(假设
	      以=作为输入序列的结束),并根据读入的元
	      素符号逐一分析
	      \begin{enumerate}
		      \item 当遇到的是一个操作数,则压入栈顶
		      \item 当遇到的是一个运算符, 就从栈中两次取出栈顶,按照运算符对这两个操作数进行计算。然后将计算结果压入栈顶
	      \end{enumerate}
	\item 如此继续,直到遇到符号=,这时栈顶的值就
	      是输入表达式的值
\end{itemize}
\begin{longlisting}
	\caption{后缀表达式计算器}
	\cppfile[firstline=1,lastline=16]{third_party/coding/cxx/datastruct/linear/include/calculator.hpp}
	\label{code:calculator}
\end{longlisting}
\subsection{单调栈}
单调栈是一种特殊类型的栈数据结构，它的特点是栈中的元素自底向上保持单调递增或单调递减的顺序。核心思想：单调栈通过在元素入栈时维护栈的单调性，从而在处理某些问题时能够高效地找到左边或右边第一个比当前元素大（或小）的元素。工作原理：当一个新元素准备入栈时，单调栈会遵循以下规则：
\begin{itemize}
	\item 单调递增栈： 如果新元素比栈顶元素小或相等，为了保持栈的递增性，我们会将栈顶元素依次弹出，直到栈为空或者栈顶元素比新元素小为止，然后将新元素压入栈中。
	\item 单调递减栈： 如果新元素比栈顶元素大或相等，为了保持栈的递减性，我们会将栈顶元素依次弹出，直到栈为空或者栈顶元素比新元素大为止，然后将新元素压入栈中。
\end{itemize}
单调栈在解决以下类型的问题时非常有用：
\begin{itemize}
	\item 寻找数组中每个元素左边/右边第一个更大的元素： 这是单调栈最经典的应用。通过维护一个单调递减栈，当一个新元素入栈时，栈中被弹出的元素就是新元素右边第一个比它大的元素，而栈顶元素则是新元素左边第一个比它大的元素（如果存在）。类似地，使用单调递增栈可以找到第一个更小的元素。
	\item 计算直方图中的最大矩形面积： 我们可以利用单调栈找到每个柱子左右两边第一个比它矮的柱子，从而确定以该柱子为高的最大矩形的宽度。
\end{itemize}
以寻找右边第一个大于当前元素的数为例，正常我们需要遍历数组将其和其后面的所有元素依次比较。这样时间复杂度为$O(n^2)$。但是如果使用单调栈时间复杂度可以为$O(n)$。
\subsection{函数递归调用}
\begin{itemize}
	\item 阶乘
	      \begin{equation*}
		      f(n) =
		      \begin{cases}
			      x\times f(n-1)\quad  n\geq 1 \\
			      1\quad n=1
		      \end{cases}
	      \end{equation*}
	\item 递归出口
	      \begin{itemize}
		      \item 递归终止的条件,即最小子问题的求解
		      \item 可以允许多个出口
	      \end{itemize}
	\item  递归规则(递归体+界函数)
	      \begin{itemize}
		      \item  将原问题划分成子问题
		      \item  保证递归的规模向出口条件靠拢
	      \end{itemize}
\end{itemize}
hanoi(n,X,Y,Z)
\begin{itemize}
	\item  移动n个环
	\item  X柱出发,将环移动到Z 柱
	\item  X、Y、Z都可以暂存(大盘不能压小盘)
\end{itemize}
河内塔示意图\nameref{fig:hanoi_tower}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=\textwidth]{hanoi_tower}
	\caption{河内塔示意图}
	\label{fig:hanoi_tower}
\end{figure}
\begin{longlisting}
	\cppfile[firstline=2,lastline=15]{third_party/coding/cxx/algorithm/recursion/src/hanoi.cc}
\end{longlisting}
递归调转示意图:\nameref{fig:ds_19}
\begin{figure}[!ht]
	\centering
	\includegraphics[width=0.5\textwidth]{ds_19}
	\caption{递归转非递归}
        \label{fig:ds_19}
\end{figure}
递归运行时，堆栈的进退以及通过堆栈传递参数
\begin{figure}[!ht]
	\centering
	\includegraphics[width=0.5\textwidth]{ds_20}
	\caption{递归运行}
	\label{fig:ds_20}
\end{figure}

\begin{equation*}
	\begin{cases}
		n+1\quad n<2 \quad \\
		f(n/2)*f(n/4) \quad n\geq 2
	\end{cases}
\end{equation*}
\begin{cpp}
void exmp(int n,int & f)
{
  int u1, u2;
  if (n<2)
    f = n+1;
  else {
    exmp((int)(n/2), u1);
    exmp((int)(n/4), u2);
    f = u1*u2;
  }
}
\end{cpp}
\subsection{队列}
队列是一个简单的序列，在尾部加入元素时队列加长，在前端删除数据时队列缩短。和栈不同，队列是两端的结构：一端用来加入新元素，另一端用来删除元素。因此最后一个元素必须等到排在它之前的所有元素都删除后才能操作。队列是一种先进先出（FIFO）的结构。下面使用一维数组实现循环数组。循环数组作为一种数据结构只是在代码层面对这种结构做限制。如图\ref{fig:queue_circle}.判断循环队列有两种方式：
\begin{enumerate}\label{en:isfull}
	\item 第一个元素在第一个单元。最后一个元素在最后一个单元（a）。
	\item 第一个元素和最后一个元素相邻并在其右面。
\end{enumerate}
enqueue()可以看成循环数组上的操作(c)，但实际上这是在一维数组上操作。因此，如果最后一个元素在最后一个单元中，而且数组的开始单元为空，则将新元素放在开始单元（d）。如果最后一个元素在其它位置，且空间允许的话，新的元素就放到它的后面（e）。
循环队列结构：
\begin{figure}
	\centering
	\includegraphics[width=\textwidth]{queue_circle}
	\caption{循环队列}
	\label{fig:queue_circle}
\end{figure}
% \cppfile{code/DS/ex8/array_queue.hpp}
测试代码:
% \cppfile{code/DS/ex8/main.cpp}
% \cppfile[firstline=49,lastline=52]{code/DS/ex8/array_queue.hpp}
上面代码测试循环队列是否已满,如\ref{en:isfull}。
enqueue的时候有两种情况一种是（d）对应的最后一个元素在数组最后面，这个时候需要将一维数组的第一个元素作为环形队列的最后一个元素添加，last指向一维数组的第一个元素如果环形队列为空，则第一个元素指向一维数组的0位置。
% \cppfile[firstline=23,lastline=29]{code/DS/ex8/array_queue.hpp}
出队包含三种情况：
\begin{enumerate}
	\item 第一个元素和最后一个元素指针指向同一个元素（指空）。
	\item first指向last-1，因为是环形队列，下一个元素就是first=0。
	\item first指针后移动一位。
\end{enumerate}
\begin{longlisting}
	\caption{单端队列的ADT}
	\cppfile[firstline=4,lastline=16]{third_party/coding/cxx/datastruct/linear/include/queue.hpp}
	\label{code:queue}
\end{longlisting}

\subsection{优先队列}
在优先队列中，根据元素的优先级以及在队列中的当前位置决定出队列的顺序。在STL中实现了优先队列priority\_queue，priority\_queue容器默认使用deque容器总是把右边即最高的元素放在队列的最前方以维持队列的顺序。为此插入push操作使用两个参数的的bool函数，将对列中的元素重新排序以满足这个要求，该函数可以使用<运算符，元素的值越大优先级越高。如果元素值越小优先级越高则需要使用函数greater表明在决定邮件队列中插入新元素push()应该应用运算符>而不是<。
优先队列的例子：
% \cppfile{code/DS/ex9/main.cpp}
对类Person中年龄最大的输出。
% \cppfile{code/DS/ex10//main.cpp}
\subsection{双端队列}
队列是一种先入先出的数据结构，\figref{fig:common_queue}对于给定长度的队列如果指定元素到达队列末尾，通常认为队列已满，即使弹出元素后此队列有多余空间。为此我们可以使用循环队列解决此问题。
\begin{figure}[!htbp]
	\centering
	\includegraphics*[width=0.8\textwidth]{queue}
	\caption{普通队列浪费存储空间}
	\label{fig:common_queue}
\end{figure}
\figref{fig:dequeue}双端队列可以解决存储空间的问题：
\begin{figure}[!htbp]
	\centering
	\includegraphics*[width=\textwidth]{dequeue}
	\caption{双端队列}
	\label{fig:dequeue}
\end{figure}
双端队列需要实现的方法：
\begin{itemize}
	\item[isEmpty] 判断队列是否为空。
	\item[isFull] 判断队列是否已满。
	\item[enQueue] 入队。
	\item[deQueue] 出队。
	\item[Front] 获取队列最前面的元素。
	\item[Rear] 获取队列尾部元素。
\end{itemize}
为此需要成员变量：
\begin{itemize}
	\item head：指向双端队列队首元素。
	\item tai：指向双端队列队尾元素。
	\item size：队列长度。
	\item count：队列中元素个数。
\end{itemize}
队列头文件如下：
% \cppfile{code/DS/MyCircularQueue/include/MyCircularQueue.h}
函数实现：
% \cppfile{code/DS/MyCircularQueue/src/MyCircularQueue.cpp}
\subsection{队列的应用}
\begin{itemize}
	\item BFS遍历
\end{itemize}
队列实现的BFS模版：
\begin{cpp}
int BFS(Node root, Node target) {
  Queue<Node> queue;  // store all nodes which are waiting to be processed
  int step = 0;       // number of steps neeeded from root to current node
  // 添加元素入队列操作，出队需要判断队列是否为空
  add root to queue;
  // BFS
  while (queue is not empty) {
    step = step + 1;
    // 遍历队列中的每个元素，将每个元素的邻接点加入队列
    int size = queue.size();
    for (int i = 0; i < size; ++i) {
      Node cur = the first node in queue;
      return step if cur is target;
      for (Node next : the neighbors of cur) {
        // add next to queue;
      	}
      // remove the first node from queue;
  }
  }
return -1;          // there is no path from root to target
}
\end{cpp}
有时，确保我们永远不会访问一个结点两次很重要。否则，我们可能陷入无限循环。如果是这样，我们可以在上面的代码中添加一个哈希集来解决这个问题。这是修改后的伪代码：
\begin{cpp}
int BFS(Node root, Node target) {
  Queue<Node> queue;  // store all nodes which are waiting to be processed
  Set<Node> used;     // store all the used nodes
  int step = 0;       // number of steps neeeded from root to current node
  // initialize
  add root to queue;
  add root to used;
  // BFS
  while (queue is not empty) {
    step = step + 1;
    // iterate the nodes which are already in the queue
    int size = queue.size();
    for (int i = 0; i < size; ++i) {
      Node cur = the first node in queue;
      return step if cur is target;
      for (Node next : the neighbors of cur) {
      	// 加入节点是否访问过的判断。
      	if (next is not in used) {
          // add next to queue;
          // add next to used;
      	}
}
      // remove the first node from queue;
}
}
return -1;          // there is no path from root to target
}
\end{cpp}
通常在二叉树的遍历中不需要使用hash结构，因为在此结构中不存在一个叶子节点同时属于两个节点。
